/*
 * @lc app=leetcode.cn id=5 lang=java
 *
 * [5] 最长回文子串
 *
 * https://leetcode-cn.com/problems/longest-palindromic-substring/description/
 *
 * algorithms
 * Medium (27.84%)
 * Likes:    1566
 * Dislikes: 0
 * Total Accepted:    155.3K
 * Total Submissions: 557.6K
 * Testcase Example:  '"babad"'
 *
 * 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
 *
 * 示例 1：
 *
 * 输入: "babad"
 * 输出: "bab"
 * 注意: "aba" 也是一个有效答案。
 *
 *
 * 示例 2：
 *
 * 输入: "cbbd"
 * 输出: "bb"
 *
 *
 */

// @lc code=start
class Solution {
    public String longestPalindrome(String s) {
        if(s.length() == 0) return "";
        int left = 0, right = 0;
        boolean dp[][] = new boolean[s.length()][s.length()];
        for(int col = 0; col < s.length(); col++){
            for(int row= 0; row <= col; row++) {
                if(col == row) {
                    dp[row][col] = true;
                    continue;
                }
                if(col - row == 1) {
                    dp[row][col] = s.charAt(row) == s.charAt(col) ? true : false;
                    if(dp[row][col] && col - row > right - left ) {
                        left = row;
                        right = col;
                    }
                    continue;
                }
                dp[row][col] = s.charAt(row) == s.charAt(col) && dp[row+1][col-1] ? true : false;
                    if(dp[row][col] && col - row > right - left) {
                        left = row;
                        right = col;
                    }
            }
        }
        return s.substring(left, right+1);
    }
}
// @lc code=end

